from 第21天.数据结构 import LinkedList


class Stack:
    def __init__(self):
        self._list = []

    def is_empty(self):
        """
        判断栈是否为空
        :return:
        """
        return len(self._list) == 0

    def push(self, element):
        """
        进栈，O(1)
        :param element:
        :return:
        """
        self._list.append(element)

    def pop(self):
        """
        出栈，O(1)
        :return:
        """
        if self.is_empty():
            return None
        return self._list.pop()

    def get_top(self):
        """
        查看栈顶，O(1)
        :return:
        """
        if self.is_empty():
            return None
        return self._list[-1]


class StackV2:
    def __init__(self):
        self._list = LinkedList()

    def is_empty(self):
        return self._list.is_empty()

    def push(self, element):
        """
        O(1)
        :param element:
        :return:
        """
        return self._list.append(element)

    def pop(self):
        """
        O(1)
        :return:
        """
        return self._list.pop()

    def get_top(self):
        """
        O(1)
        :return:
        """
        return self._list[len(self._list) - 1]


# 判断一个字符串中的括号情况是否匹配

target_str = "([{]}"


def brace_match(brace_str: str) -> bool:
    stack = Stack()
    for l in brace_str:
        if l in ["(", "[", "{"]:
            stack.push(l)
        elif l in [")", "]", "}"]:
            top = stack.pop()
            if top == "(" and l == ")":
                continue
            elif top == "[" and l == "]":
                continue
            elif top == "{" and l == "}":
                continue
            else:
                return False
    return stack.is_empty()


if __name__ == "__main__":
    case_1 = "()[]{}"
    case_2 = "([{}])"
    case_3 = "([]{}"
    case_4 = "([}{])"

    print(brace_match(case_1))
    print(brace_match(case_2))
    print(brace_match(case_3))
    print(brace_match(case_4))

